#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>

using namespace std;

typedef std::vector<int> VectorInt;
typedef std::vector<std::pair<int, int>> VectorPair;

// 动态规划问题
// Dynamic Programming
namespace {

// 斐波那契数列求和
// 菲波那切数列：f(1) = 1, f(2) = 1, f(n) = f(n - 1) + f(n - 2)

// 直接递归复杂度O(2^n)
int fib(int n) {
    if (n == 1 || n == 2) return 1;
    return fib(n - 1) + fib(n - 2);
}

// 保存中间和，避免重复计算，复杂度O(n)，额外空间复杂度O(n)
// 自顶向下的计算方法
int fib2(VectorInt &sums, int n) {
    if (n == 1 || n == 2) return 1;
    if (sums[n] != 0) return sums[n];
    sums[n] = fib2(sums, n - 1) + fib2(sums, n - 2);
    return sums[n];
}

int fib2(int n) {
    // 存储1->n的和
    VectorInt sums(n + 1, 0);
    return fib2(sums, n);
}

// 自底向上计算
int fib3(int n) {
    // 存储1->n的和
    VectorInt dp(n + 1, 0);
    dp[1] = 1; dp[2] = 1;
    for (int i=3; i<=n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    return dp[n];
}

int fib4(int n) {
    if (n == 1 || n == 2) return 1;
    int sum = 1;
    int pre1 = 1, pre2 = 1;
    for (int i=3; i<=n; i++) {
        sum = pre1 + pre2;
        pre1 = pre2;
        pre2 = sum;
    }
    return sum;
}

// 硬币凑整问题
/* 题目
给你 k 种面值的硬币，面值分别为 c1, c2 ... ck，每种硬币的数量无限，再给一个总金额 amount，
问你最少需要几枚硬币凑出这个金额，如果不可能凑出，算法返回 -1
*/
int coinChange(vector<int>& coins, int amount) {
    // 数组大小为 amount + 1，初始值也为 amount + 1
    // 凑足amount金额最多amount个，用 amount + 1表示一个极大值
    vector<int> dp(amount + 1, amount + 1);
    // base case
    dp[0] = 0;
    for (int i = 0; i < dp.size(); i++) {
        // 内层 for 在求所有子问题 + 1 的最小值
        for (int coin : coins) {
            // 子问题无解，跳过
            // i金额一下的只能用小i的凑
            if (i - coin < 0) continue;
            dp[i] = min(dp[i], 1 + dp[i - coin]);
        }
    }
    return (dp[amount] == amount + 1) ? -1 : dp[amount];
}

// 最短编辑距离
// 已知 s1 = horse, s2 = ros 求 s1 变成 s2 需要编辑的最小次数
// 编辑操作包括：增加，删除，替换
// 方法是，两个指针分别执行字符串末尾，依次向前操作，每次操作从增删改中取最小的次数
int minDistanceDp(const string &s1, const string &s2, int i, int j) {
    // base case
    if (i < 0) return j + 1; // s1遍历完，则继续s2操作
    if (j < 0) return i + 1; // s2遍历完，则继续s1操作

    if (s1[i] == s2[j]) {
        // 字符相等，操作数不变，两指针同时向前
        return minDistanceDp(s1, s2, i - 1, j - 1);
    }
    else {
        return std::min({
        minDistanceDp(s1, s2, i - 1, j) + 1,        // s1删除一个字符，s1向前
        minDistanceDp(s1, s2, i, j - 1) + 1,        // s2增加一个字符，s2向前
        minDistanceDp(s1, s2, i - 1, j - 1) + 1     // 替换字符，同时向前
        }, std::less<int>());
    }
}

int minDistanceDp2(const string &s1, const string &s2, int i, int j, vector<vector<int>> &dp) {
    if (i < 0) return j + 1;
    if (j < 0) return i + 1;
    
    if (dp[i][j] >= 0) return dp[i][j];
    
    if (s1[i] == s2[j]) {
        dp[i][j] = minDistanceDp2(s1, s2, i - 1, j - 1, dp);
    }
    else {
        dp[i][j] = std::min({
        minDistanceDp2(s1, s2, i - 1, j, dp) + 1,
        minDistanceDp2(s1, s2, i, j - 1, dp) + 1,
        minDistanceDp2(s1, s2, i - 1, j - 1, dp) + 1
        }, std::less<int>());
    }
    return dp[i][j];
}

int minDistanceDp3(const string &s1, const string &s2, int i, int j, vector<VectorPair> &dp) {
    // base case
    if (i < 0) return j + 1; // s1遍历完，则继续s2操作
    if (j < 0) return i + 1; // s2遍历完，则继续s1操作

    if (dp[i][j].first >= 0) {
        return dp[i][j].first;
    }

    if (s1[i] == s2[j]) {
        // 字符相等，操作数不变，两指针同时向前
        dp[i][j].first = minDistanceDp3(s1, s2, i - 1, j - 1, dp);
    }
    else {
        int a = minDistanceDp3(s1, s2, i - 1, j, dp) + 1;        // s1删除一个字符，s1向前
        int b = minDistanceDp3(s1, s2, i, j - 1, dp) + 1;        // s1增加一个字符，s2向前
        int c = minDistanceDp3(s1, s2, i - 1, j - 1, dp) + 1;    // 替换字符，同时向前
        if (a < b && a < c) {
            dp[i][j].first = a;
            dp[i][j].second = 2;
        }
        else if (b < a && b < c) {
            dp[i][j].first = b;
            dp[i][j].second = 1;
        }
        else {
            dp[i][j].first = c;
            dp[i][j].second = 3;
        }
    }
    return dp[i][j].first;
}

// std::pair<最小编辑数,编辑类型(0无操作，1增，2删，3改)>
int minDistance(string s1, string s2) {
    int i = s1.length();
    int j = s2.length();
    vector<VectorPair> dp(i, VectorPair(j, std::make_pair(-1, 0)));

    int ret = minDistanceDp3(s1, s2, i - 1, j - 1, dp);

    int choice;
    int m = i - 1;
    int n = j - 1;
    int len = max(i, j);
    string temp = s1;
    std::cout << s1 << " -> " << s2 << std::endl;
    std::cout << temp << std::endl;
    for (len--; len>=0; len--) {
        if (m < 0)
            choice = 1;
        else if (n < 0)
            choice = 2;
        else
            choice = dp[m][n].second;
        
        if (choice == 1) {
            temp.insert(max(0, m), 1, s2[n]);
            n--;
        }
        else if (choice == 2) {
            temp.erase(m, 1);
            m--;
        }
        else if (choice == 3) {
            temp.replace(m, 1, 1, s2[n]);
            n--;
            m--;
        }
        else {
            n--;
            m--;
        }
        choice > 0 && std::cout << temp << std::endl;
    }

    return ret;
}

// 非递归方法
int minDistance2(string s1, string s2) {
    int m = s1.length();
    int n = s2.length();
    vector<VectorInt> dp(m+1, VectorInt(n+1));

    for (int i=1; i<=m; i++)
        dp[i][0] = i;
    for (int j=1; j<=n; j++)
        dp[0][j] = j;

    for (int i=1; i<=m; i++) {
        for (int j=1; j<=n; j++) {
            if (s1[i - 1] == s2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1];
            }
            else {
                dp[i][j] = std::min({
                    dp[i - 1][j] + 1,
                    dp[i][j - 1] + 1,
                    dp[i - 1][j - 1] + 1
                }, std::less<int>());
            }
        }
    }

    return dp[m][n];
}

void Handle() {
    int n = 20;
    std::cout << "fib n: " << n << std::endl;
    std::cout << "fib: " << fib(n) << std::endl;
    std::cout << "fib2: " << fib2(n) << std::endl;
    std::cout << "fib3: " << fib3(n) << std::endl;
    std::cout << "fib4: " << fib4(n) << std::endl;

    VectorInt coins = {1, 3, 5};
    int amount = 11;
    std::cout << "coinChange: " << coinChange(coins, amount) << std::endl;

    string s1 = "dinitrophenylhydrazine";
    string s2 = "benzalphenylhydrazone";
    int n1 = s1.length();
    int n2 = s2.length();
    minDistance(s1, s2);
    std::cout << "minDistance2: " << minDistance2(s1, s2) << std::endl;

    vector<VectorInt> dp(n1, VectorInt(n2, -1));
    std::cout << "minDistanceDp2: " << minDistanceDp2(s1, s2, n1-1, n2-1, dp) << std::endl;

    // std::cout << "minDistanceDp: " << minDistanceDp(s1, s2, n1-1, n2-1) << std::endl;
}
}

void HandleDp() {
    Handle();
}